package Top_Interview_Questions_Review._001Tree;

import Top_Interview_Questions_Review._001Tree.Supple.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/6 21:38
 * <p>
 * 功能描述:
 */
public class _0094 {

    /**
     * 第一遍解题:  2020/1/6 21:38
     * 参考gitee
     * leetcode/problems/94.binary-tree-inorder-traversal.md
LeetCodeAnimation/notes/LeetCode第94号问题：二叉树的中序遍历.md
     *
     * 假设输入样例为:
     *          1
     *        /   \
     *      NULL   2
     *           /  \
     *          3   NULL
     *        /  \
     *       4    5
     *
     *
     * 解析:
     * 1.(root != null || !stack.empty()) 这个条件的原因?根据上面的输入样例,当循环
     * 到4节点时,栈中从低到高为2-3-4。此时4.right=null,list中仅有1,显然还没有执行完。
     * 然而此时root=4.right=null,而只有当root!=null时才能执行循环,为了执行循环要加个
     * !stack.empty()
     * 2.迭代过程看上面两个参考
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }


    //递归
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal1(TreeNode root) {
        helper(root);
        return res;
    }

    public void helper(TreeNode root){
        if(root == null){
            return ;
        }

        helper(root.left);
        res.add(root.val);
        helper(root.right);
    }
}

